package com.jsn.buildbase.algorithm;

import android.util.Pair;

import androidx.annotation.NonNull;
import androidx.annotation.Nullable;
import androidx.core.view.ViewCompat;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class ltcdj {


    //
    /*class Solution {
public:
    int flag = 1;
    Node* connect(Node* root) {
        if(!root)return nullptr;
        if(flag){  // 将根节点next置为null
            root->next = nullptr;
            flag = 0;
        }
        if(!root->left) return root;
        root->left->next = root->right;
        if(root->next)root->right->next = root->next->left;
        else root->right->next = nullptr;
        connect(root->left);
        connect(root->right);
        return root;
    }
}; */

    /*[1,2,2,3,3,null,null,4,4]*/

/*
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int depth1 = depth(root.left);
        int depth2 = depth(root.right);
        if(depth1==-1 || depth2==-1 ){
            return false;
        }
        return (Math.abs(depth(root.left)-depth(root.right))<=1)
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public  int depth(TreeNode root){ //max depth
        if(root==null) {
            return 0;
        }
        int depth1 = depth(root.left);
        int depth2 = depth(root.right);
        if(Math.abs(depth1-depth2)>1) return -1;
        int depth= Math.max(depth1,depth2)+1;
        return depth;
    }*/





    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    Queue<Node> queue=new LinkedList<>();

    ArrayList<Node> nodes = new ArrayList<>();



    public int maxDepth(Node root) {
        int depth=0;
        if(root==null) return 0;
        queue.add(root);
        depth++;

        Node poll;
        while(!queue.isEmpty()){
            nodes.clear();
            while ((poll=queue.poll())!=null){
                nodes.add(poll);
            }
            for (Node node : nodes) {
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            if(queue.isEmpty()) depth++;
        }


        return depth;


    }

    public Node connect(Node root) {
        if(root==null) return null;
        queue.add(root);

        while(!queue.isEmpty()){
            nodes.clear();
            Node node;
            while ((node=queue.poll())!=null){
                nodes.add(node);
            } // poll to the list
            for (Node node1 : nodes) {
                if(node1.left!=null){
                    queue.add(node1.left);
                }if(node1.right!=null){
                    queue.add(node1.right);
                }
            }//add children  to queue

            //link node
            for(int i=0;i<nodes.size();i++){
                if(i+1<=nodes.size()-1){
                    nodes.get(i).next=nodes.get(i+1);
                }
            }
        }

        return root;
    }



    public Node _connect(Node root) {
        if(root==null) return null;
        if(root.left!=null){
            root.left.next=root.right;
            if(root.next!=null){
                root.right.next=root.next.left;
            }
            connect(root.left);
            connect(root.right);
        }
        return root;
    }

    private void link(Queue<Node> queue) {
        Queue<Node> temp=new LinkedList<>();
        temp.addAll(queue);
        Node node;
        while((node=temp.poll())!=null){
            Node peek = queue.peek();
            if(peek!=null) node.next=peek;
        }
    }
}
